package com.LeeCode;

/**
 * 美丽下标对的数目
 */

public class Code2748 {
    public static void main(String[] args) {
        int[] nums = {2, 5, 1, 4};
        System.out.println(new Code2748().countBeautifulPairs(nums));
    }

    public int countBeautifulPairs(int[] nums) {
        int[] cnt = new int[10];
        int ans = 0;
        for (int num : nums) {
            int index = num % 10;
            for (int i = 1; i < 10; i++) {
                if (gcd(index, i) == 1)
                    ans += cnt[i];
            }
            while (num > 10) num /= 10;
            cnt[num]++;
        }
        return ans;
    }

    private int gcd(int a, int b) {
        while (a != 0) {
            int temp = a;
            a = b % a;
            b = temp;
        }
        return b;
    }
}
